{
	class Node {
		constructor(
			public data: number | null = null,
			public Left: Node | null = null,
			public right: Node | null = null
		) {}

		public show(): number | null {
			return this.data
		}
	}

	class BST {
		constructor(public root: Node | null = null) {}

		public insert(data: number) {
			let node = new Node(data, null, null)
			// 如果根为空 直接插入
			if (this.root === null) {
				this.root = node
				return
			}
			// 根据二叉搜索树规则插入
			let current = this.root
			let parent
			while (true) {
				parent = current
				if (parent.data && data < parent.data) {
					current = current.Left as Node
					if (!current) {
						parent.Left = node
						break
					}
				} else {
					current = current.right as Node
					if (!current) {
						parent.right = node
						break
					}
				}
			}
		}

		// 先序遍历
		public preOrder(root: Node) {
			if (root) {
				console.log(root.data)
				this.preOrder(root.Left as Node)
				this.preOrder(root.right as Node)
			}
		}

		// 中序遍历
		public inOrder(root: Node) {
			if (root) {
				this.inOrder(root.Left as Node)
				console.log(root.data)
				this.inOrder(root.right as Node)
			}
		}

		// 后续遍历
		public postOrder(root: Node) {
			if (root) {
				this.postOrder(root.Left as Node)
				this.postOrder(root.right as Node)
				console.log(root.data)
			}
		}

		// 获取最小值
		public getMin(): number {
			let current = this.root
			while (current && current.Left) {
				current = current.Left
			}
			return (current && current.data) as number
		}

		// 获取最大值
		public getMax(): number {
			let current = this.root
			while (current && current.right) {
				current = current.right
			}
			return (current && current.data) as number
		}

		// 查找节点
		public find(data: number): Node | null {
			let current = this.root
			while (current) {
				if (current && current.data === data) {
					return current
				} else if (current && (current.data as number) < data) {
					current = current.right
				} else if (current && (current.data as number) > data) {
					current = current.Left
				}
			}
			return null
		}

		// 删除节点
		public remove(data: number) {
			this.root = this.removeNode(this.root as Node, data)
		}

		private removeNode(node: Node, data: number): Node | null {
			if (!node) {
				return null
			}
			if (data === node.data) {
				// 叶子节点
				if (!node.Left && !node.right) {
					return null
				}
				// 没有左节点
				if (!node.Left) {
					return node.right
				}
				// 没有右节点
				if (!node.right) {
					return node.Left
				}
				// 有两个子节点的节点
				let tempNode = this.getMinNode(node.right)
				node.data = tempNode.data
				node.right = this.removeNode(node.right, tempNode.data as number)
				return node
			} else if (data < (node.data as number)) {
				node.Left = this.removeNode(node.Left as Node, data)
				return node
			} else {
				node.right = this.removeNode(node.right as Node, data)
				return node
			}
		}

		private getMinNode(node: Node): Node {
			let current = node
			while (current && current.Left) {
				current = current.Left
			}
			return current
		}
	}

	let nums = new BST()
	// nums.root
	nums.insert(23)
	nums.insert(45)
	nums.insert(16)
	nums.insert(37)
	nums.insert(3)
	nums.insert(99)
	nums.insert(22)
	// nums.inOrder(nums.root as Node)
	nums.preOrder(nums.root as Node)
	// nums.postOrder(nums.root as Node)
	console.log('min', nums.getMin())
	console.log('max', nums.getMax())
	console.log('find', nums.find(7))
	nums.remove(23)
	// nums.preOrder(nums.root as Node)
	// nums.inOrder(nums.root as Node)
}
